package com.xiaohe66.demo.arithmetic.leetcode.math;

/**
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 * 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 *
 * <p>
 * 示例 1：
 * 输入：n = 12
 * 输出：3
 * 解释：12 = 4 + 4 + 4
 *
 * <p>
 * 示例 2：
 * 输入：n = 13
 * 输出：2
 * 解释：13 = 4 + 9
 *
 * <p>
 * 提示：
 * 1 <= n <= 104
 *
 * <p>
 * 通过次数148,404提交次数242,332
 *
 * @author xiaohe
 * @time 2021.06.11 10:04
 */
public class T279完全平方数 {

    /**
     * 设数组sq, sq[i]表示i的平方，i <= 200。
     * 那么原题变成：从sq中选取若干个数，使其结果等于 n
     * 设dp[i][j],表示从前i个sq中选取和等于j的最小数量
     * 当 i = 1时， dp[1][j] = j
     * 对于每个dp[i][j]都有选和不选。
     * 若 j < sq[i]，则不可选, dp[i] = dp[i-1][j];
     * 若 j>= sq[i]，则：
     * 不选：dp[i][j] = dp[i-1][j]
     * 选：dp[i][j] = dp[i-1][j - sq[i]]
     * 结果选取上面2种情况的最小值
     * dp[length][n] 便是最终返回值
     *
     * <p>
     * 执行用时：29 ms, 在所有 Java 提交中击败了88.80%的用户
     * 内存消耗：37.5 MB, 在所有 Java 提交中击败了64.39%的用户
     */
    public int numSquares(int n) {

        // 滚动数组
        int[] dp = new int[n + 1];
        int max = (int) Math.sqrt(n);

        for (int j = 0; j <= n; j++) {
            dp[j] = j;
        }

        for (int i = 2; i <= max; i++) {
            int sq = i * i;
            // 正序遍历 ： 由于每一个数可以使用多次，因此尽量使用新更新的值，也就是最小值。
            for (int j = sq; j <= n; j++) {

                dp[j] = Math.min(dp[j - sq] + 1, dp[j]);
            }
        }

        return dp[n];
    }

}
